package fireway;

import java.util.NoSuchElementException;

/**
 * 循环队列
 * 没有数据项计数字段的队列实现
 * 2018年 04月 05日 星期四
 *
 * @author fireway
 */
public class Queue {
    // The queued items
    private long[] mItems;

    // 队头
    private int mFront;

    // 队尾
    private int mRear;

    private static final long NULL_Element = 0L;

    public Queue(int initialCapacity) {
        mItems = new long[initialCapacity];

        for (int i = 0; i < mItems.length; i++) {
            mItems[i] = NULL_Element;
        }

        mFront = 0;
        mRear = -1;
    }

    public boolean add(long e) {
        if (isFull()) {
            throw new IllegalStateException("Queue full: rear = " + mRear
                                            + ", front =" + mFront);
        } else {
            insert(e);
            return true;
        }
    }

    public boolean offer(long e) {
        if (isFull()) {
            System.out.println("Queue full: rear = " + mRear + ", front ="
                               + mFront);
            return false;
        } else {
            insert(e);
            return true;
        }
    }

    public long poll() {
        if (isEmpty()) {
            System.out.println("Queue empty: rear = " + mRear + ", front ="
                               + mFront);
            return NULL_Element;
        } else {
            return extract();
        }
    }

    public long remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue empty: rear = " + mRear
                                             + ", front =" + mFront);
        } else {
            return extract();
        }
    }

    /**
     * 获取但不移除此队列的头
     */
    public long peek() {
        if (isEmpty()) {
            return NULL_Element;
        } else {
            return mItems[mFront];
        }
    }

    public boolean isEmpty() {
        circularlyReset();

        if ((mRear + 1 == mFront) && (mItems[mFront + 1] == NULL_Element)) {
            return true;
        } else {
            return false;
        }
    }

    public boolean isFull() {
        circularlyReset();

        if ((mRear + 1 == mFront) && mItems[mFront + 1] != NULL_Element) {
            return true;
        } else {
            return false;
        }
    }

    public int size() {
        if (isEmpty()) {
            return 0;
        }

        if (mRear >= mFront) {
            return mRear + 1 - mFront;
        } else {
            return mRear + 1 - mFront + mItems.length;
        }
    }

    private void insert(long e) {
        circularlyReset();
        mItems[++mRear] = e;
    }

    private long extract() {
        circularlyReset();
        long tmp = mItems[mFront];
        mItems[mFront] = NULL_Element;
        mFront++;
        return tmp;
    }

    private void circularlyReset() {
        if (mItems.length - 1 == mRear) {
            mRear = -1;
        }

        if (mItems.length == mFront) {
            mFront = 0;
        }
    }
}
